
import java.util.Arrays;

/**
 * Author:kongguoguang
 * Date:2020/8/25
 * Time:15:56
 * Summary:
 */
public class BinaryTreeTest {

    public static void main(String[] args) {

        Integer[] intArray = new Integer[]{1,2,3,4,5,null,6};

        TreeNode[] tree = intArrayToBinaryTree(intArray);

        System.out.println(Arrays.toString(getAverageOfEachLayer(tree)));

    }

    /**
     * 整型数组转为二叉树，树的节点以数组方式存放
     */
    private static TreeNode[] intArrayToBinaryTree(Integer[] intArray){
        if (intArray == null || intArray.length == 0){
            return null;
        }

        //先将int数值转为TreeNode对象并存放到数组中
        TreeNode[] treeNodes = new TreeNode[intArray.length + 1];
        int length = intArray.length;
        for (int i = 0; i < length; i++){
            if (intArray[i] != null){
                treeNodes[i+1] = new TreeNode(intArray[i]);
            }
        }

        //再给TreeNode对象添加左右子节点
        length = treeNodes.length;
        for (int j = 1; j < length; j++){

            if (treeNodes[j] == null){
                continue;
            }

            if (j * 2 < length){
                treeNodes[j].left = treeNodes[j * 2];
            }

            if (j * 2 + 1 < length){
                treeNodes[j].right = treeNodes[j * 2 + 1];
            }

        }

        return treeNodes;
    }

    /**
     * 计算每一层的平均值，保存到数组中
     */
    private static float[] getAverageOfEachLayer(TreeNode[] tree){
        if (tree == null || tree.length == 0){
            System.out.println("error parameter");
            return null;
        }

        int layers = getNumberOfLayers(tree[1]);
        System.out.println("The number of this tree layers is = " + layers);

        float[] average = new float[layers];

        //计算每一层的平均值
        for (int i = 1; i <= layers; i++){
            int count = 0;
            int sum = 0;
            //数组形式存放的二叉树，每一层节点在数组中的下标满足如下公式
            // 2的i-1次方 <= 节点下标 < 2的i次方， i为层数
            //可根据这一公式遍历每层的节点
            for (int j = (int) Math.pow(2, i-1); j < Math.pow(2, i); j++){
                if (j >= tree.length){
                    break;
                }

                if (tree[j] != null){
                    count++;
                    sum += tree[j].value;
                }
            }
            average[i -1] = (float) (sum * 1.0 / count);
        }

        return average;
    }

    /**
     * 计算二叉树层数
     */
    private static int getNumberOfLayers(TreeNode treeNode){
        if (treeNode == null) {
            return 0;
        }
        return Math.max(getNumberOfLayers(treeNode.left), getNumberOfLayers(treeNode.right)) + 1;
    }

    public static class TreeNode {

        int value;

        TreeNode  left;

        TreeNode  right;

        public TreeNode(int value) {
            this.value = value;
        }
    }
}
